import java.util.Arrays;

public class MergeSort {
    static {
        System.out.println("归并排序");
    }
    public static int[] mergeSort(int[] arr){
        if (arr.length<2)
            return arr;
        int mid=arr.length/2;
        int[] left= Arrays.copyOfRange(arr,0,mid);
        int[] right= Arrays.copyOfRange(arr,mid,arr.length);

        return merge(mergeSort(left),mergeSort(right));
    }
    private static int[] merge(int[] left,int[] right){
        int[]  res=new int[left.length+right.length];
        for(int index=0,i=0,j=0;index<res.length;index++){

            if (i>=left.length)//右边数组元素有剩余
                res[index]=right[j++];
            else if (j>=right.length)//左边数组元素有剩余
                res[index]=left[i++];
            else if (left[i]<right[j])
                res[index]=left[i++];
            else
                res[index]=right[j++];
        }
        return res;
    }
}
